package graph.topsort;

import java.util.*;

/**
 * 拓扑排序  判断图中是否成环
 *
 * 清晰的说明 https://leetcode-cn.com/problems/course-schedule/solution/bao-mu-shi-ti-jie-shou-ba-shou-da-tong-tuo-bu-pai-/
 *
 * 把一个 有向无环图 转成 线性的排序 就叫 拓扑排序
 * bfs 就是统计每个点的入度  以及每个节点的后续节点关联关系 两个hashmap
 * 随着节点出队 修改后续节点入度 及自身入度
 * 全部节点出队后如果还有节点入度不为0  表示有环
 */
public class 课程表_207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];     // 每个节点的入度
        Map<Integer, List<Integer>> nodeRel = new HashMap<>();// 节点与后续节点的映射关系
        Queue<Integer> queue = new LinkedList<>();
        // 添加入度表及邻接关系表
        for (int[] prerequisite : prerequisites) {  // [0,3] 表示  0之前必须学习课程3  因此 3 -> 0
            int cur = prerequisite[0];   // 0
            int pre = prerequisite[1];   // 3
            inDegree[cur] ++;  // 修改cur 入度
            List<Integer> nexts = nodeRel.computeIfAbsent(pre, k -> new ArrayList<>()); // 添加到映射关系中
            nexts.add(cur);
        }
        // 扫描入度为0的点入队
        for (int node = 0; node < numCourses; node++) {
            if(inDegree[node] == 0)
                queue.offer(node);
        }
        int zeroInDegreeCnt = 0;
        // bfs
        while( !queue.isEmpty()) {
            int cur = queue.poll(); // 出队 表示该课程学习完了  其入度已经是0 无序修改
            zeroInDegreeCnt ++; // 入度为0 的节点统计
            List<Integer> nexts = nodeRel.get(cur);
            zeroInDegreeCnt ++; // 入度为0 的节点统计
            for(Integer next : nexts) {
                if( --inDegree[next] == 0 ) {  // 后续节点入度都减一  如果为0  表示不依赖任何前面的节点 可以进入队列学习
                    queue.offer(next);
                }
            }
        }
        // 也可以这样做
        /*for (int id : inDegree) {     如果还有入度不为0 的节点  表示有环
            if(id > 0) return  false;
        }*/

        return zeroInDegreeCnt == numCourses; // 如果所有节点入度都为0 表示全学习完了
    }
}
